{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Minimum Number of Fibonacci Numbers Whose Sum Is K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinFibonacciNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为 K 的最少斐波那契数字数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你数字 <code>k</code>&nbsp;，请你返回和为&nbsp;<code>k</code>&nbsp;的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。</p>\n",
    "\n",
    "<p>斐波那契数字定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>F<sub>1</sub> = 1</li>\n",
    "\t<li>F<sub>2</sub> = 1</li>\n",
    "\t<li>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub>&nbsp;， 其中 n &gt; 2 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数据保证对于给定的 <code>k</code>&nbsp;，一定能找到可行解。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>k = 7\n",
    "<strong>输出：</strong>2 \n",
    "<strong>解释：</strong>斐波那契数字为：1，1，2，3，5，8，13，&hellip;&hellip;\n",
    "对于 k = 7 ，我们可以得到 2 + 5 = 7 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>k = 10\n",
    "<strong>输出：</strong>2 \n",
    "<strong>解释：</strong>对于 k = 10 ，我们可以得到 2 + 8 = 10 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>k = 19\n",
    "<strong>输出：</strong>3 \n",
    "<strong>解释：</strong>对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k](https://leetcode.cn/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k](https://leetcode.cn/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7', '10', '19']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        cnt = 0\n",
    "        while k:\n",
    "            i,j = 1,1\n",
    "            while j <= k:\n",
    "                tmp = i+j\n",
    "                i = j\n",
    "                j = tmp\n",
    "            k -= i\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        lst=[1,1]\n",
    "        while lst[-2]+lst[-1]<=k:\n",
    "            lst.append(lst[-2]+lst[-1])\n",
    "        ans=0\n",
    "        i=len(lst)-1\n",
    "        while k>0:\n",
    "            if lst[i]<=k:\n",
    "                k-=lst[i]\n",
    "                ans+=1\n",
    "            i-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        lst=[1,1]\n",
    "        while lst[-2]+lst[-1]<=k:\n",
    "            lst.append(lst[-2]+lst[-1])\n",
    "        ans=0\n",
    "        i=len(lst)-1\n",
    "        while k>0:\n",
    "            if lst[i]<=k:\n",
    "                k-=lst[i]\n",
    "                ans+=1\n",
    "            i-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1,1]\n",
    "        a = f[0]\n",
    "        b = f[1]\n",
    "        c = 0\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1]+f[-2])\n",
    "        res = 0\n",
    "        i = len(f)-1\n",
    "        while k :\n",
    "            if k>= f[i]:\n",
    "                k -= f[i]\n",
    "                res += 1\n",
    "            i -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        x, y = 1, 1\n",
    "        while y <= k:\n",
    "            x, y = y, x + y\n",
    "        if x == k:\n",
    "            return 1\n",
    "        else:\n",
    "            return self.findMinFibonacciNumbers(k - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        dp = [1,1]\n",
    "        while dp[-1] <= k:\n",
    "            dp.append(dp[-1]+dp[-2])\n",
    "        cnt = 0\n",
    "        i = len(dp)-2\n",
    "        while k > 0:\n",
    "            if k >= dp[i]:\n",
    "                cnt += k//dp[i]\n",
    "                k %= dp[i]\n",
    "            i -= 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        x, y = 1, 1\n",
    "        while y <= k:\n",
    "            x, y = y, x + y\n",
    "        if x == k:\n",
    "            return 1\n",
    "        else:\n",
    "            return self.findMinFibonacciNumbers(k - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        def get_fib(k):\n",
    "            x, y = 1, 1\n",
    "            while y <= k:\n",
    "                x, y = y, x + y\n",
    "            if x == k:\n",
    "                return 1\n",
    "            else:\n",
    "                return get_fib(k - x) + 1\n",
    "        return get_fib(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        count = 0\n",
    "        i = len(f) - 1\n",
    "        while k > 0:\n",
    "            if k >= f[i]:\n",
    "                k -=f[i]\n",
    "                count += 1\n",
    "            i -=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fb = [1,1]\n",
    "        while fb[-1]+fb[-2]<=k:\n",
    "            fb.append(fb[-1]+fb[-2])\n",
    "        fbsum,res = 0,0\n",
    "        n =len(fb)-1\n",
    "        while fbsum!=k:\n",
    "            if fbsum+fb[n]>k:\n",
    "                n-=1\n",
    "            else:\n",
    "                fbsum+=fb[n]\n",
    "                res+=1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1,1]\n",
    "        while f[-1] < k :\n",
    "            f.append(f[-1] + f[-2])\n",
    "        ans = 0\n",
    "        i = len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fib = [0, 1]\n",
    "        while fib[-1] < k:\n",
    "            fib.append(fib[-1] + fib[-2])\n",
    "\n",
    "        res = 0\n",
    "        l = len(fib) - 1\n",
    "        while k:\n",
    "            if k >= fib[l]:\n",
    "                k -= fib[l]\n",
    "                res += 1\n",
    "            l -= 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int: \n",
    "        if k == 1:\n",
    "            return 1\n",
    "        fn = [1,1]\n",
    "        while fn[-1] + fn[-2] <= k:\n",
    "            curr = fn[-1] + fn[-2]\n",
    "            if curr == k:\n",
    "                return 1\n",
    "            fn.append(curr)\n",
    "\n",
    "        n = 2\n",
    "        num = k - fn[-1]\n",
    "        while not num in fn:\n",
    "            n += 1\n",
    "            low, high = 0, len(fn) - 1\n",
    "            mid = 0\n",
    "            near = 0\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if fn[mid] < num:\n",
    "                    low = mid + 1\n",
    "                    near = fn[mid]\n",
    "                else: \n",
    "                    high = mid - 1\n",
    "            num -= near\n",
    "        # dfs\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        lst=[1,1]\n",
    "        while lst[-2]+lst[-1]<=k:\n",
    "            lst.append(lst[-2]+lst[-1])\n",
    "        ans=0\n",
    "        i=len(lst)-1\n",
    "        while k>0:\n",
    "            if lst[i]<=k:\n",
    "                k-=lst[i]\n",
    "                ans+=1\n",
    "            i-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        x, y = 1, 1\n",
    "        while y <= k:\n",
    "            x, y = y, x + y\n",
    "        if x == k:\n",
    "            return 1\n",
    "        else:\n",
    "            return self.findMinFibonacciNumbers(k - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        i = len(f) - 1\n",
    "        res = 0\n",
    "        while k > 0:\n",
    "            if f[i] <= k:\n",
    "                k -= f[i]\n",
    "                res += 1\n",
    "            i -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        num_cached = self.buildFibonacci(k)\n",
    "        return self.helper(k, 0, num_cached)\n",
    "        pass\n",
    "\n",
    "    def helper(self, k, result, num_cached: list):\n",
    "        if k == 0:\n",
    "            return result\n",
    "        if k < 0:\n",
    "            return None\n",
    "        for num in num_cached[::-1]:\n",
    "            if k - num >= 0:\n",
    "                sub_res = self.helper(k - num, result + 1, num_cached)\n",
    "                if sub_res != None:\n",
    "                    return sub_res\n",
    "            pass\n",
    "        else:\n",
    "            return k\n",
    "\n",
    "        pass\n",
    "\n",
    "    def buildFibonacci(self, k):\n",
    "        result = []\n",
    "        end = k\n",
    "        result.append(1)\n",
    "        result.append(1)\n",
    "        cur = 2\n",
    "        while cur <= end:\n",
    "            result.append(result[-1] + result[-2])\n",
    "            cur = result[-1]\n",
    "            pass\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr,limit=[1,1],10**9\n",
    "while arr[-1]<=limit:\n",
    "    arr.append(arr[-1]+arr[-2])\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        ans=0\n",
    "        while k>0:\n",
    "            j=bisect_right(arr,k)-1\n",
    "            k-=arr[j]\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        x, y = 1, 1\n",
    "        while y <= k:\n",
    "            x, y = y, x + y\n",
    "        if x == k:\n",
    "            return 1\n",
    "        else:\n",
    "            return self.findMinFibonacciNumbers(k - x) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        if k < 2:\n",
    "            return k    \n",
    "\n",
    "        fib = [0, 1]\n",
    "        while fib[-1] <= k:\n",
    "            fib.append(fib[-1] + fib[-2])\n",
    "        return self.findMinFibonacciNumbers(k - fib[-2]) + 1\n",
    "        # res = 0\n",
    "        # l = len(fib) - 1\n",
    "        # while k:\n",
    "        #     if k >= fib[l]:\n",
    "        #         k -= fib[l]\n",
    "        #         res += 1\n",
    "        #     l -= 1\n",
    "        # return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        if(k == 1):\n",
    "            return 1\n",
    "        a, b = 1, 1\n",
    "        while(a + b < k):\n",
    "            a, b = b, a + b\n",
    "        if(a + b == k):\n",
    "            return 1\n",
    "        else:\n",
    "            return 1 + self.findMinFibonacciNumbers(k-b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f,i,a=[1,1],2,0\n",
    "        while(f[-1]<k):\n",
    "            f.append(f[i-1]+f[i-2])\n",
    "            i+=1\n",
    "        while k>0:\n",
    "            a += k//f[i-1]\n",
    "            k = k % f[i-1]\n",
    "            i-=1\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        def get_fib(k):\n",
    "            x, y = 1, 1\n",
    "            while y <= k:\n",
    "                x, y = y, x + y\n",
    "            return 1 if x == k else get_fib(k - x) + 1\n",
    "            \n",
    "        return get_fib(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr,limit=[1,1],10**9\n",
    "while arr[-1]<=limit:\n",
    "    arr.append(arr[-1]+arr[-2])\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        ans=0\n",
    "        while k>0:\n",
    "            j=bisect_right(arr,k)-1\n",
    "            k-=arr[j]\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fibs = [1, 1]\n",
    "        count = 0\n",
    "\n",
    "        while fibs[-1] < k:\n",
    "            fibs.append(fibs[-1] + fibs[-2])\n",
    "        \n",
    "        for num in reversed(fibs):\n",
    "            if k >= num:\n",
    "                k -= num\n",
    "                count += 1\n",
    "            \n",
    "            if k == 0:\n",
    "                break\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        #1, 1, 2,3,5,8,13,21, 34, 55,89,144,\n",
    "        ##k = 1e9\n",
    "        ans = 0\n",
    "        fei = [1, 1]\n",
    "        t = 2\n",
    "        while t <= 1e9:\n",
    "            fei += t,\n",
    "            t += fei[-2]\n",
    "        print(fei) \n",
    "        while k > 0:\n",
    "            k -= fei[bisect(fei, k)-1]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fib_lst = [1, 1]\n",
    "        for _ in range(k):\n",
    "            fib_lst.append(fib_lst[-1] + fib_lst[-2])\n",
    "            if fib_lst[-1] > k:\n",
    "                break\n",
    "\n",
    "        res = 0\n",
    "        while k > 0:\n",
    "            if k >= fib_lst[-1]:\n",
    "                k -= fib_lst[-1]\n",
    "                res += 1\n",
    "\n",
    "                if k in fib_lst:\n",
    "                    return res + 1\n",
    "            else:\n",
    "                fib_lst.pop()\n",
    "                \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        ans = 0\n",
    "        i = len(f) - 1\n",
    "        while k > 0:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fibs = [1, 1]\n",
    "        count = 0\n",
    "\n",
    "        while fibs[-1] < k:\n",
    "            fibs.append(fibs[-1] + fibs[-2])\n",
    "        \n",
    "        for num in reversed(fibs):\n",
    "            if k >= num:\n",
    "                k -= num\n",
    "                count += 1\n",
    "            \n",
    "            if k == 0:\n",
    "                break\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        # S(n) = Fn + Fn-1 + Fn-2 + ...\n",
    "        # S(n) = Fn + S(n-1)\n",
    "        # S(n) < 2 * S(n)\n",
    "        F = [1, 1] + self.produce(k)\n",
    "        F = F[::-1]\n",
    "        result = 0\n",
    "        for num in F:\n",
    "            if num <= k:\n",
    "                k -= num\n",
    "                result += 1\n",
    "        return result\n",
    "\n",
    "    def produce(self, k, first = 1, second = 1):\n",
    "        now = first + second\n",
    "        if now > k:\n",
    "            return []\n",
    "        else:\n",
    "            return [now] + self.produce(k, second, now)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "不断生成fib numbers, 知道最后的number 大于k\n",
    "\n",
    "k = 19,\n",
    "fibs = [1, 1, 2, 3, 5, 8, 13]\n",
    "\n",
    "然后reverse fibs，如果k 大于num, 就不断减少，计算次数\n",
    "直到k等于0停止\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fibs = [1, 1]\n",
    "        count = 0\n",
    "\n",
    "        while fibs[-1] < k:\n",
    "            fibs.append(fibs[-1] + fibs[-2])\n",
    "        \n",
    "        for num in reversed(fibs):\n",
    "            if k >= num:\n",
    "                k -= num\n",
    "                count += 1\n",
    "            \n",
    "            if k == 0:\n",
    "                break\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        # 因为存在数字1，且每个数字可以被使用多次因此k必定有解\n",
    "        a1 = 1\n",
    "        a2 = 1\n",
    "        l = [1] * 46\n",
    "        for i in range(1,46):\n",
    "            a1,a2 = a2,a1 + a2\n",
    "            l[i] = a2\n",
    "        result = 0\n",
    "        for j in range(45,-1,-1):\n",
    "            if k == 0:\n",
    "                break\n",
    "            if k >= l[j]:\n",
    "                k -= l[j]\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fibonacci = [1, 1]\r\n",
    "while fibonacci[-1] < 10 ** 9:\r\n",
    "    fibonacci.append(fibonacci[-1] + fibonacci[-2])\r\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        for i in range(len(fibonacci) - 1, -1, -1):\r\n",
    "            if fibonacci[i] <= k:\r\n",
    "                k -= fibonacci[i]\r\n",
    "                if k == 0:\r\n",
    "                    return 1\r\n",
    "                return self.findMinFibonacciNumbers(k) + 1\r\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int: \n",
    "        f = [1,1]\n",
    "        r = 0\n",
    "        while True:\n",
    "            if k == 0:\n",
    "                return r\n",
    "            if f[-1] >= k:\n",
    "                i=bisect_right(f, k)\n",
    "                k = k-f[i-1]\n",
    "                r += 1\n",
    "            else:\n",
    "                f.append(f[-1]+f[-2])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        nums = [1,1]\n",
    "        while nums[-1]<k:\n",
    "            nums.append(nums[-1]+nums[-2])\n",
    "        res = 0\n",
    "        idx = -1\n",
    "        while k>0:\n",
    "            while nums[idx]>k:\n",
    "                idx -=1\n",
    "            k -= nums[idx]\n",
    "            res += 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] + f[-2] <= k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        \n",
    "        # print(f)\n",
    "\n",
    "        r = 0\n",
    "        while k != 0:\n",
    "            # print(f'k:{k} f:{f}')\n",
    "\n",
    "            while f[-1] > k:\n",
    "                f.pop(-1)\n",
    "            r += 1\n",
    "            k -= f[-1]\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        num_cached = self.buildFibonacci(k)\n",
    "        return self.helper(k, 0, num_cached)\n",
    "        pass\n",
    "\n",
    "    def helper(self, k, result, num_cached: list):\n",
    "        if k == 0:\n",
    "            return result\n",
    "        if k < 0:\n",
    "            return None\n",
    "        for num in num_cached[::-1]:\n",
    "            if k - num >= 0:\n",
    "                sub_res = self.helper(k - num, result + 1, num_cached)\n",
    "                if sub_res != None:\n",
    "                    return sub_res\n",
    "            pass\n",
    "        else:\n",
    "            return k\n",
    "\n",
    "        pass\n",
    "\n",
    "    def buildFibonacci(self, k):\n",
    "        result = []\n",
    "        end = k\n",
    "        result.append(1)\n",
    "        result.append(1)\n",
    "        cur = 2\n",
    "        while cur <= end:\n",
    "            result.append(result[-1] + result[-2])\n",
    "            cur = result[-1]\n",
    "            pass\n",
    "        return result\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        def get_fib(k):\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            x, y = 1, 1\n",
    "            while y <= k:\n",
    "                x, y = y, x + y\n",
    "            return get_fib(k - x) + 1\n",
    "        return get_fib(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        def binarySearch(arr, num):\n",
    "            left, right = -1, len(arr)\n",
    "            while left + 1 != right:\n",
    "                mid = left + ((right - left) >> 1)\n",
    "                if arr[mid] <= num: left = mid\n",
    "                else: right = mid\n",
    "            return left\n",
    "\n",
    "        # 特判\n",
    "        # if k == 0: return 0\n",
    "        # if k == 1: return 1\n",
    "\n",
    "        # 打表，生成小于k的所有斐波那契数\n",
    "        fs = [1,1]\n",
    "        while fs[-1] + fs[-2] <= k:\n",
    "            fs.append(fs[-1] + fs[-2])\n",
    "        \n",
    "        # 找到不超过k值的最大数（由于该题的数据范围较小，斐波那契数的长度不长，所以就算逐个遍历也会很快）\n",
    "        ans = 0\n",
    "        while k:\n",
    "            max_fb = fs[binarySearch(fs, k)]\n",
    "            ans += k // max_fb\n",
    "            k %= max_fb\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_right(nums, val)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        #1, 1, 2,3,5,8,13,21, 34, 55,89,144,\n",
    "        ##k = 1e9\n",
    "        ans = 0\n",
    "        fei = [1, 1]\n",
    "        t = 2\n",
    "        while t <= 1e9:\n",
    "            fei += t,\n",
    "            t += fei[-2]\n",
    "        print(fei) \n",
    "        while k > 0:\n",
    "            k -= fei[bisect(fei, k)-1]\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        # 生成所有小于或等于 k 的斐波那契数\n",
    "        fibs = [1, 1]\n",
    "        while fibs[-1] + fibs[-2] <= k:\n",
    "            fibs.append(fibs[-1] + fibs[-2])\n",
    "        \n",
    "        # 使用贪心算法找到和为 k 的斐波那契数字的最少数目\n",
    "        count = 0\n",
    "        for fib in reversed(fibs):\n",
    "            if k >= fib:\n",
    "                k -= fib\n",
    "                count += 1\n",
    "            if k == 0:\n",
    "                break\n",
    "        \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        if(k == 1):\n",
    "            return 1\n",
    "        a, b = 1, 1\n",
    "        while(a + b < k):\n",
    "            a, b= b, a+b\n",
    "        if(a + b == k):\n",
    "            return 1\n",
    "        else:\n",
    "            return 1 + self.findMinFibonacciNumbers(k-b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fb = [1,1]\n",
    "        res = 0\n",
    "        while fb[-1]+fb[-2]<=k:\n",
    "            fb.append(fb[-1]+fb[-2])\n",
    "        for i in range(len(fb)-1,-1,-1):\n",
    "            if fb[i]<=k:\n",
    "                res+=1\n",
    "                k -=fb[i]\n",
    "            if k==0:\n",
    "                return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arr,limit=[1,1],10**9\n",
    "while arr[-1]<=limit:\n",
    "    arr.append(arr[-1]+arr[-2])\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        #贪心,每次选取小于等于k的最大斐波那契数字,为了方便寻找可以预处理出来。\n",
    "        ans=0\n",
    "        while k>0:\n",
    "            j=bisect_right(arr,k)-1\n",
    "            k-=arr[j]\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        F = [1, 1]\n",
    "        while F[-2] + F[-1] <= k:\n",
    "            F.append(F[-2]+F[-1])\n",
    "        ans = 0\n",
    "        for i in range(len(F)-1, -1, -1):\n",
    "            if k - F[i] >= 0:\n",
    "                ans += 1\n",
    "                k -= F[i]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-2] + f[-1])\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "            print(f)\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# * 贪心\n",
    "# https://leetcode.cn/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/solutions/212767/he-wei-k-de-zui-shao-fei-bo-na-qi-shu-zi-shu-mu-by/\n",
    "class Solution1:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        f = [1, 1]\n",
    "        while f[-1] < k:\n",
    "            f.append(f[-1] + f[-2])\n",
    "\n",
    "        ans, i = 0, len(f) - 1\n",
    "        while k:\n",
    "            if k >= f[i]:\n",
    "                k -= f[i]\n",
    "                ans += 1\n",
    "\n",
    "            i -= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "# 贪心+二分查找\n",
    "ceil = 10**9\n",
    "dp = [1, 1]\n",
    "while True:\n",
    "    dp.append(dp[-2] + dp[-1])\n",
    "    if dp[-1] > ceil:\n",
    "        break\n",
    "\n",
    "class Solution2:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        ans = 0\n",
    "        while k:\n",
    "            i = bisect.bisect_right(dp, k)\n",
    "            k -= dp[i - 1]\n",
    "            ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "ceil = 10**9\n",
    "dp = [1, 1]\n",
    "while True:\n",
    "    dp.append(dp[-2] + dp[-1])\n",
    "    if dp[-1] > ceil:\n",
    "        break\n",
    "\n",
    "dp.reverse()\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while k:\n",
    "            if k >= dp[i]:\n",
    "                k -= dp[i]\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        fibo = [1, 1]\n",
    "        while fibo[-1] <= k:\n",
    "            fibo.append(fibo[-1] + fibo[-2])\n",
    "        fibo.reverse()\n",
    "        result = 0\n",
    "\n",
    "        def dfs(i, count, vsum, target):\n",
    "            nonlocal result\n",
    "            if vsum == target:\n",
    "                result = count\n",
    "                return True\n",
    "            if vsum > target:\n",
    "                return False\n",
    "            if i == len(fibo):\n",
    "                return False\n",
    "            for j in range(0, len(fibo)):\n",
    "                if dfs(j, count+1, vsum+fibo[j], target):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        if dfs(0, 0, 0, k):\n",
    "            return result\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_left(nums, val)\r\n",
    "            if ind < len(nums) and nums[ind] == val:\r\n",
    "                return(1)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_right(nums, val)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_left(nums, val)\r\n",
    "            if ind < len(nums) and nums[ind] == val:\r\n",
    "                return(1)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_right(nums, val)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_right(nums, val)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\r\n",
    "        nums = [1, 2]\r\n",
    "        while(nums[-1] + nums[-2] <= k):\r\n",
    "            nums.append(nums[-1] + nums[-2])\r\n",
    "        \r\n",
    "        def get_num(val):\r\n",
    "            if val == 0:\r\n",
    "                return(0)\r\n",
    "            ind = bisect_left(nums, val)\r\n",
    "            if ind < len(nums) and nums[ind] == val:\r\n",
    "                return(1)\r\n",
    "            return(get_num(val - nums[ind - 1]) + 1)\r\n",
    "        return(get_num(k))\r\n",
    "\r\n",
    "        # dp = [float('inf')] * (k + 1)\r\n",
    "        # dp[0] = 0\r\n",
    "        # for i in range(1, k + 1):\r\n",
    "        #     for v in nums:\r\n",
    "        #         if i - v >= 0:\r\n",
    "        #             dp[i] = min(dp[i], dp[i - v] + 1)\r\n",
    "        #         else:\r\n",
    "        #             break\r\n",
    "        # return(dp[-1])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findMinFibonacciNumbers(self, k: int) -> int:\n",
    "        x, y = 1, 1\n",
    "        while y <= k:\n",
    "            x, y = y, x + y\n",
    "        if x == k:\n",
    "            return 1\n",
    "        else:\n",
    "            return self.findMinFibonacciNumbers(k - x) + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
